#ifndef MGGS_BST
#define MGGS_BST

#define BLACK false
#define RED true

#include "TNode.h"
#include <iostream>
#include <cstdlib>
#include <algorithm>

template<typename T>
class BinaryTree
{
public:
 protected:
    TNode<T>* root;
 public:
    BinaryTree() {root = NULL;};
    BinaryTree(int _point, T _data);
    ~BinaryTree();
    void release(TNode<T>* _x);
    int isempty();
    TNode<T>* tree_search(T _data) const;
    TNode<T>* find(int _point, TNode<T>* _x);
    TNode<T>* find(int _point);
    TNode<T>* min(TNode<T>* _x) const;
    TNode<T>* min() const;
    TNode<T>* max(TNode<T>* _x) const;
    TNode<T>* max() const;
    TNode<T>* successor(TNode<T>* _x) const;
    TNode<T>* predecessor(TNode<T>* _x) const;
    void insert(TNode<T>* _p);
    void insert(int point, T _data);
    void transplant(TNode<T> *_u, TNode<T> *_v);
    void del(TNode<T> *_x);
    void RightRotate(TNode<T>* _x);
    void LeftRotate(TNode<T>* _x);
    void set_parent(TNode<T>* _x, TNode<T>* _y);
};


template<typename T>
BinaryTree<T>::BinaryTree(int _point, T _data)
{
  TNode<T>* p = new TNode<T>(_point,_data);
    if (root == NULL)
	root = p;
};

template<typename T>
void BinaryTree<T>::release(TNode<T>* _x)
{
    if (_x != NULL)
    {
	release(_x->lc);
	release(_x->rc);
	delete _x;
    }	
};


template<typename T>
BinaryTree<T>::~BinaryTree()
{
    release(root);
};

template<typename T>
int BinaryTree<T>::isempty()
{
  if (root != NULL)
    return 0;
  else
    return 1;
}

template<typename T>
TNode<T>* BinaryTree<T>::successor(TNode<T>* _x) const
{
    TNode<T>* x = _x;
    if (x->rc != NULL)
	return min(x->rc);
    TNode<T>* y = x->parent;
    while (y != NULL && x == y->rc)
    {
	x = y;
	y = y->parent;
    }
    return y;
};


template<typename T>
TNode<T>* BinaryTree<T>::predecessor(TNode<T>* _x) const
{
  TNode<T>* x = _x;
  if (x->lc != NULL)
    return max(x->lc);
  TNode<T>* y = x->parent;
  while (y != NULL && x == y->lc){
    x = y;
    y = y->parent;
  }
  return y;
}

template<typename T>
TNode<T>* BinaryTree<T>::min(TNode<T>* _x) const
{
    while (_x->lc != NULL)
	_x = _x->lc;
    return _x;
};

template<typename T>
TNode<T>* BinaryTree<T>::min() const
{
  if (root != NULL)
    return this->min(root);
}

template<typename T>
TNode<T>* BinaryTree<T>::max(TNode<T>* _x) const
{
  while (_x->rc != NULL)
    _x = _x->rc;
  return _x;
}

template<typename T>
TNode<T>* BinaryTree<T>::max() const
{
  if (root != NULL)
    return this->max(root);
}

template<typename T>
void BinaryTree<T>::insert(TNode<T>* _p){
    TNode<T>* y = NULL;
    TNode<T>* x = root;
    while (x != NULL)
    {
	y = x;
	if (_p->data  < x->data)
	    x = x->lc;
	else
	    x = x->rc;
    }
    _p->parent = y;
    if (y == NULL)
	root = _p;
    else if (_p->data < y->data)
	y->lc = _p;
    else
	y->rc = _p;
}


template<typename T>
void BinaryTree<T>::insert(int _point, T _data)
{
    TNode<T>* p = new TNode<T>(_point,_data);
    this->insert(p);
}


template<typename T>
TNode<T>* BinaryTree<T>::tree_search(T _data) const
{
  TNode<T>* x = root;
  while (x != NULL){
    if (x->data > _data)
      x = x->lc;
    else if (x->data < _data)
      x = x->rc;
    else
      return x;
  }
  return NULL;
}

template<typename T>
TNode<T>* BinaryTree<T>::find(int _point, TNode<T>* _x)
{
  TNode<T>* y = NULL;
  if (_x != NULL){
    if (_x->point == _point)
      return _x;
    y = find(_point,_x->lc);
    if (y != NULL)
      return y;
    y = find(_point,_x->rc);
    if (y != NULL)
      return y;
  }
    return NULL;
}

template<typename T>
TNode<T>* BinaryTree<T>::find(int _point)
{
    return this->find(_point,root);;
}


template<typename T>
void BinaryTree<T>::transplant(TNode<T> *_u, TNode<T> *_v){
  if (_u == NULL){
    std::cerr << "Error! Can not transplant to a NULL."
                  << std::endl;
    std::exit(-1);
  }
  if (_u->parent == NULL)
    root = _v;  
  else if (_u == _u->parent->lc)
    _u->parent->lc = _v;
  else
    _u->parent->rc = _v;
  if (_v != NULL)
    _v->parent = _u->parent;
}

template<typename T>
void BinaryTree<T>::del(TNode<T> *_x){
  if (_x != NULL){
    if (_x->lc == NULL)
      this->transplant(_x, _x->rc);
    else if (_x->rc == NULL)
      this->transplant(_x, _x->lc);
    else{
      TNode<T> *y = min(_x->rc);
      if (y->parent != _x){
	this->transplant(y, y->rc);
	y->rc = _x->rc;
	y->rc->parent = y;
      }
      this->transplant(_x, y);
      y->lc = _x->lc;
      y->lc->parent = y;
    }
    delete _x;
  }
}



template<typename T>
void BinaryTree<T>::RightRotate(TNode<T>* _x){
  TNode<T>* y = _x->lc;
  _x->lc = y->rc;
  if (y->rc != NULL)
    y->rc->parent = _x;
  y->parent = _x->parent;
  if (_x->parent == NULL)
    root = y;
  else if (_x == _x->parent->lc)
    _x->parent->lc = y;
  else
    _x->parent->rc = y;
  y->rc = _x;
  _x->parent = y;
}


template<typename T>
void BinaryTree<T>::LeftRotate(TNode<T>* _x){
  TNode<T>* y = _x->rc;
  _x->rc = y->lc;
  if (y->lc != NULL)
    y->lc->parent = _x;
  y->parent = _x->parent;
  if (_x->parent == NULL)
    root = y;
  else if (_x == _x->parent->lc)
    _x->parent->lc = y;
  else
    _x->parent->rc = y;
  y->lc = _x;
  _x->parent = y;
}

template<typename T>
void BinaryTree<T>::set_parent(TNode<T>* _x, TNode<T>* _y)
{
  _y->parent = _x;
}

#else
// DO NOTHING.
#endif
